package ua.mykola.ds.stack;

import java.util.Deque;

/**
 * Reverse a stack without using extra space.
 */
public class ReverseStack {

	public <T> Deque<T> reverse(Deque<T> stack) {
		if (stack.size() == 0)
			return stack;
		T pop = stack.pop();
		Deque<T> reversed = reverse(stack);
		appendToBottom(reversed, pop);

		return reversed;
	}

	private <T> void appendToBottom(Deque<T> stack, T element) {
		if (stack.size() == 0) {
			stack.push(element);
		} else {
			T pop = stack.pop();
			appendToBottom(stack, element);
			stack.push(pop);
		}
	}

}
